from itertools import permutations

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(permutations(nums))


# 下面也可以
class Solution2:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 1:
            return [nums]
        res = []
        for seq in self.permute(nums[1:]):
            for i in range(len(seq) + 1):
                res.append(seq[:i] + [nums[0]] + seq[i:])
        return res
